#ifndef _GRAPH_H_
#define _GRAPH_H_

#include <iostream>
#include <stdlib.h>
#include <vector>
using namespace std;

#define INFINITY 100000

//边结点
struct EdgeNode
{
    int point;//终点
    int weight;//权重
    EdgeNode *next;//指向的下一条边
};
//点结点
struct VertexNode
{
    int vertex;//起始点
    EdgeNode *edge;//指向的第一条边
};

class Graph
{
public:
    vector <VertexNode> a;//存放点节点的向量
    int vertexnum;//点数
    int edgenum;//边数
    Graph();//构造函数
    void Dijkstra(int v);//Dijkstra算法函数
};

Graph :: Graph()
{
    cout << "please input the number of vertexs and edges" <<endl;
    cin >> vertexnum >> edgenum;

    for(int i=0;i<=vertexnum;i++)
    {
        VertexNode x;
        x.vertex=i;
        x.edge=NULL;
        a.push_back(x);
    }
    
    cout << "please input the startpoint,endpoint,and weight" <<endl;
    for(int i=0;i<edgenum;i++)
    {
        int s=0,e=0,w=0;
        cin >> s >> e >> w;
        EdgeNode *x;
        x=new EdgeNode;
        x->point=e;
        x->weight=w;
        x->next=a[s].edge;
        a[s].edge=x;    
    }
}

void Graph :: Dijkstra(int v)
{
    EdgeNode *temp;
    int min,k;
    vector <int> Final,kn;
    for(int i=0;i<=vertexnum;i++)
    {
        Final.push_back(0);
        kn.push_back(0);
    }
    for(int i=1;i<=vertexnum;i++)
    {
        if(i==v)
        {
            temp=a[i].edge;
            Final[i]=0;
            kn[i]=1;
        }
        else
        {
            Final[i]=INFINITY;
            kn[i]=0;
        }
    }
    while(temp)
    {
        Final[temp->point]=temp->weight;
        temp=temp->next;
    }
    min=INFINITY;
    for(int i=1;i<=vertexnum;i++)
    {
        while(temp)
        {
            if(kn[temp->point]==0 && temp->weight+min<Final[temp->point])
            {
                Final[temp->point]=temp->weight+min;
            }
            temp=temp->next;
        }
        min=INFINITY;
        for(int j=1;j<=vertexnum;j++)
        {
            if(min>Final[j] && Final[j]!=0 && kn[j]==0)
            {
                min=Final[j];
                k=j;
            }
        }
        kn[k]=1;
        temp=a[k].edge;
    }
    for(int i=1;i<=vertexnum;i++)
    {
        if(Final[i]>=INFINITY)
        {
            cout << "there is no way from " << v << " to " << i << endl;
        }
        else
        {
            cout << "the distance from " << v << " to " << i << " is " << Final[i]<< endl;
        }
    }
}




#endif